#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 505, INF = 0x3f3f3f3f;

int c, n, sp, m;
int g[N][N], dist[N], store[N];
bool st[N];
vector<int> pre[N];
vector<int> path, res_path;
int back = INF, send = INF;

void Dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0;
    
    for (int i = 0; i <= n; i ++ ) {
        int t = -1;
        for (int j = 0; j <= n; j ++ ) {
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }
        st[t] = true;
        
        for (int j = 0; j <= n; j ++ ) {
            if (dist[j] > dist[t] + g[t][j]) {
                dist[j] = dist[t] + g[t][j];
                pre[j].clear();
                pre[j].push_back(t);
            } else if (dist[j] == dist[t] + g[t][j])
                pre[j].push_back(t);
        }
    }
    
}

void DFS(int u) {
    path.push_back(u);
    // 出口，计算当前序列需要带出和带回的数量
    if (u == 0) {
        int tback = 0, tsend = 0;
        // 逆序遍历保证正向序列遍历
        for (int i = path.size() - 1; i >= 0; i -- ) {
            
            int p = path[i];
            
            if (store[p] > 0) tback += store[p];
            else if (store[p] < 0) {
                if (tback + store[p] >= 0) tback += store[p];
                else tsend += -(tback + store[p]), tback = 0;
            }
        }
        
        if (tsend < send || (tsend == send && tback < back)) {
            send = tsend;
            back = tback;
            res_path = path;
        }
        
        path.pop_back();
        return;
    }
    
    for (int i = 0; i < pre[u].size(); i ++) 
        DFS(pre[u][i]);
    
    path.pop_back();
    return ;
}

int main() {
    cin >> c >> n >> sp >> m;
    for (int i = 1; i <= n; i ++ ) {
        int a;
        cin >> a;
        store[i] = a - c / 2;
    }
    
    memset(g, INF, sizeof g);
    for (int i = 1; i <= m; i ++ ) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a][b] = g[b][a] = w;
    }
    
    Dijkstra();
    
    DFS(sp);
    
    reverse(res_path.begin(), res_path.end());
    
    cout << send << " 0";
    for (int i = 1; i < res_path.size(); i ++ ) {
        cout << "->" << res_path[i];
    }
    cout << " " << back << endl;
    return 0;
}
